Regardless of the size of a computer and, in particular, of its internal memory, there are always some practical limits to the size of program which it can run. One such limit is imposed by the maximum direct jump which may be allowed in an executable module in order to carry out instructions usually relating to a module which is linked into the executable module at link time. In such cases, at the initial stage of compilation, upon detecting a reference to another module, the compiler does not know the address at which the other module will be referenced. It is therefore normal procedure to leave a vacancy in the compiled code for accommodating a direct jump to a new address, so that during linking, the appropriate address can be inserted into the vacancy. If when the linker attends to the linkage of external modules, the required direct jump which must be inserted into the vacancy in the main code exceeds the maximum permitted direct jump, there is currently no straightforward way in which the program can be compiled successfully.
The maximum permitted range (otherwise known as "branch scope") which may be achieved by a single direct jump is dependent on the number of bits which are allocated for referencing a target address. Thus, at the level of assembler code, each jump instruction includes an opcode (jmp) followed by the target address to which the program must branch. Typically, two or three bytes are reserved for referencing the target address and therefore any target address which is so large that it cannot be represented by these two bytes, simply cannot be reached. For the sake of completeness, it should be noted that direct jumps contemplate both absolute and relative jumps. Relative jumps move the program counter to a target address location which is displaced from the source address by a specified value. In distinction thereto, absolute jumps specify the target address absolutely. Usually, relative jumps are of short range and the required displacement can therefore be stored without problem. However, relative jumps are not constrained to operate over short ranges only, and it might therefore occur that the displacement required for a relative direct jump exceeds the maximum permitted range.
It follows from the above that computer programs can be compiled only to the extent that the maximum direct jump in the compiled program may be accommodated in the permitted address space. This may also have ramifications when patching existing programs which utilize the same address space in order to add features not contemplated when the program was originally compiled. Patching usually requires that the executable module be modified by adding a code segment whose start address usually follows immediately after the last instruction in the executable module. In general, this requirement can be expressed as follows. Suppose X denotes the size of a given code segment i in the input executable, and let Y be the size of code segment j in this executable. Let R denote the maximum permitted range of direct branch instruction. If X+Y&gt;R, then the segment j cannot be allocated in a way that its addresses are accessible with a single direct branch from the code segment i. For instance, if X/2+Y/2 exceeds R, then the higher half of segment j is allocated beyond the area that is accessible by a single direct branch from the lower half of segment i.
This constraint is escalating as programs grow in size since currently available linkers are not equipped to handle direct branch instructions which extend beyond the branch scope. It should be noted that even the recognition that a desired branch extends the branch scope is a much more involved process during linking than it is during patching, regardless of what steps are then taken to sidestep the problem. During patching, the complete code is intact and therefore the length of any branch is easily determined. This is far from the case when several compiled program modules are rendered into a composite executable module by the linker. It is clearly much more difficult in this case to know in advance whether a branch statement will require a jump that exceeds the branch scope, let alone take corrective action., Normally what happens is that the linker either fails or the program crashes during execution.
For the sake of completeness, it should further be observed that the program counter can also be advanced using indirect jumps. In this case, following the opcode there is given an address of a register which itself contains the target address. Since the register is not limited in size to the number of bytes allocated to the register address, the target address is not limited to the maximum permitted range. Thus, indirect addressing appears to offer a solution to the problem with which the invention is concerned. However, indirect addressing is not always suitable because it imposes the overhead of requiring an additional dedicated register. Not all registers can serve this purpose and therefore the number of registers which may be used for indirect addressing is limited. It may therefore be the case that no registers are available for storing the target address of a particular indirect jump. Thus, whilst it might appear superficially that indirect jumps always provide an acceptable solution to the limited maximum range of direct jumps, in practice this is not the case.